package MemorySearch;
/**
 * P1137 第n个泰波那契数
 * */
public class P1137 {
}


class P1137Test01{
    /*
    * 递归加动态存储
    * */
    int[] fx;
    public int tribonacci(int n) {
        fx=new int[n+5];
        return f(n);
    }

    private int f(int n){
        if(fx[n]!=0){
            return fx[n];
        }
        if(n==0)
            return 0;
        if(n==1||n==2)
            return 1;
        fx[n]=f(n-1)+f(n-2)+f(n-3);

        return fx[n];
    }
}

class P1137Test02{
    /*
     * 动态规划
     * */

    public int tribonacci(int n) {
        int[]fx=new int[n+5];
        fx[0]=0;
        fx[1]=fx[2]=1;

        for(int i=3;i<=n;i++){
            fx[i]=fx[i-1]+fx[i-2]+fx[i-3];
        }
        return fx[n];
    }
}